Авито (+РЕШЕНИЕ)

Первая задача

• 88. Merge Sorted Array РЕШЕНИЕ

• 2. Add Two Numbers РЕШЕНИЕ Единственное отличие, что в АВИТО числа это не перевернутые и в массивах хранятся:
  • input: arr1 = [1, 2, 3], arr2 = [4, 5, 6]

  • output: [0, 5, 7, 9] (один ведущий 0 в ответе допускается)

  • Note: 123 + 456 = 579

Вторая задача

• 347. Top K Frequent Elements РЕШЕНИЕ (Оптимально заO(n) по времени и O(n) по памяти, но через кучу тоже принимают хоть и не оптимально)

• 215. Kth Largest Element in an Array РЕШЕНИЕ (реже спрашивают - через кучу тоже принимают - но лучше тут конечно рассказать оптимальное решение)

• 40. Combination Sum II (оч редко спрашивают - Отличие в том, что в авито могут быть отрицательные числа еще)

• 907. Sum of Subarray Minimums #hard

Доп вопросы

• Устройство хеш-мапы. Тут скорее всего спросят про:
  • что такое коллизии

  • методы разрешения коллизий

  • оценку по времени для всех операций

  • +- как это работает конкретно в вашем ЯП

• Рассказать про структуру данных “куча”. В редких случаях могут попросить написать. Скорее всего спросят:
  • зачем нужна/примеры задач где можно применить

  • оценку по времени для операций

  • как устроена внутри +-

• Сортировки
  • Какие знаешь?

  • quick sort - сложность